1. 题目

题目链接：P2014「[CTSC1997]选课」 。

题目描述

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 NN 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 aa 是课程 bb 的先修课即只有学完了课程 aa，才能学习课程 bb）。一个学生要从这些课程里选择 MM 门课程学习，问他能获得的最大学分是多少？

输入格式

第一行有两个整数 NN，MM 用空格隔开。（1≤N≤3001 \leq N \leq 300，1≤M≤3001 \leq M \leq 300）

接下来的 NN 行,第 I+1I+1 行包含两个整数 kik_i 和 sis_i，kik_i 表示第 II 门课的直接先修课，sis_i 表示第 II 门课的学分。若 ki=0k_i=0 表示没有直接先修课（1≤ki≤N1 \leq {k_i} \leq N，1≤si≤201 \leq {s_i} \leq 20）。

输出格式

只有一行，选 MM 门课程的最大得分。

输入输出样例

输入 #1

1
2
3
4
5
6
7
8
7  4
2  2
0  1
0  4
2  1
7  1
7  6
2  2

输出 #1

1
13

2. 题解

分析

树上 dp + 背包问题的结合，即树上背包。有题意可知，最终这些课程构成一个森林，我们不妨将 00 号结点看作所有树的根，其学分为 00，则我们将森林转为一棵树来处理：

  • 首先构建状态：设 f[i][j]f[i][j] 表示以 ii 号结点为根容许选 jj 门课的子树的最大学分。

  • 然后构建状态转移方程：遍历结点 uu 的每个孩子 vv，计算转移方程

f[i][j]=max⁡1≤k≤j−1{f[i][j],f[i][j−k]+f[v][k]}f[i][j] = \max_{1 \leq k \leq j-1}\{f[i][j], f[i][j-k]+f[v][k]\}

即对于当前结点 ii 有 jj 的容量、分 kk 的容量给 vv 子树得到的最大学分。

注意

  • 首先，对于每个孩子 vv 而言，jj 应当从最大递减逆序枚举，因为需要保证 f[i][j−k]f[i][j-k] 的最优解不是来源于 vv 子树（因为 f[v][k]f[v][k] 已经是来源于 vv 子树的）。
  • 其次，遍历每个孩子 vlv_l 时 jj 的范围时不一样的。因为对于已经遍历过的子树而言，我们需要考虑其也有可能对最优解产生贡献，因此需要将 jj 的范围扩大到包括所有已遍历的子树大小（但不能超过 m+1m+1）。设 resres 为已经遍历的子树的大小之和，则 jj 的范围为

j∈[1,min(res,m+1)]j \in [1,min(res,m+1)]

  • 最后，需要计算结点 ii 所有可能容量的最优解，然后向上更新父结点。以此类推。

求解过程可以采用自顶向下的方法，即利用树的递归性质，采用 DFS 遍历整棵树，每次遍历完子树后再更新当前结点；也可以采用自底向上的方法，首先构建一个队列，将孩子数为 00 的结点加入队列中。然后从队列中取出结点开始更新，每次更新完都将父结点的孩子树减 11，然后将孩子树为 00 的父结点加入队列中（本质是一个拓扑序列，将父子结点的边看作是孩子到父亲的有向边）。

代码

DFS 计算子树最优解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
#define ll int
#define MAXN 305
using namespace std;

// 前向星存边
ll cnt;
ll head[MAXN];
struct edge{
    ll to;
    ll next;
}e[MAXN];
void init() {
    cnt = 0;
    memset(head, -1, sizeof(head));
}
void addEdge(ll u, ll v) {
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt++;
}

ll k[MAXN];         // 父结点
ll s[MAXN];         // 权值
ll dp[MAXN][MAXN];  

// dfs
ll dfs(ll u, ll m) {
    ll res = 1;
    dp[u][1] = s[u];
    for(ll i = head[u]; i != -1; i = e[i].next) {
        ll curres = dfs(e[i].to, m-1);
        // 剩余 j 门课
        for(ll j = min(res, m); j; --j) {
            for(ll ii = 1; ii <= curres && j+ii <= m; ++ii) {
                dp[u][j+ii] = max(dp[u][j+ii], dp[u][j] + dp[e[i].to][ii]);
            }
        }
        res += curres;
    }
    return res;
}

int main()
{
    ll n, m;
    init();
    scanf("%d%d", &n, &m);
    for(ll i = 1; i <= n; ++i) {
        ll ki, si;
        scanf("%d%d", &ki, &si);
        k[i] = ki;
        s[i] = si;
        addEdge(ki, i);
    }
    dfs(0, m+1);
    printf("%d\n", dp[0][m+1]);
    return 0;
}

拓扑排序计算子树最优解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
#define ll int
#define MAXN 305
using namespace std;

// 前向星存边
ll cnt;
ll head[MAXN];
struct edge{
    ll to;
    ll next;
}e[MAXN];
void init() {
    cnt = 0;
    memset(head, -1, sizeof(head));
}
void addEdge(ll u, ll v) {
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt++;
}

ll k[MAXN];         // 父结点
ll s[MAXN];         // 权值
ll in[MAXN];        // 入度
ll sz[MAXN];        // 子树大小
ll dp[MAXN][MAXN];  

void answer(ll n, ll m) {
    queue <ll> q;
    for(int i = 0; i <= n; ++i) {
        if(!in[i]) {
            dp[i][1] = s[i];
            sz[i] = 1;
            --in[k[i]];
            ++sz[k[i]];
            if(!in[k[i]]) {
                ++sz[k[i]];
                q.push(k[i]);
            }
        }
    }
    while(q.size()) {
        ll p = q.front();
        q.pop();
        ll res = 1;
        dp[p][1] = s[p];
        for(ll i = head[p]; i != -1; i = e[i].next) {
            ll u = e[i].to;
            for(ll j = min(res, m+1); j; --j) {
                for(ll d = 1; d <= sz[u] && d+j <= m+1; ++d) {
                    dp[p][d+j] = max(dp[p][d+j], dp[p][j]+dp[u][d]);
                }
            } 
            res += sz[u];
        }
        --in[k[p]];
        sz[k[p]] += sz[p];
        if(!in[k[p]]) {
            ++sz[k[p]];
            q.push(k[p]);
        }
    }
}

int main()
{
    ll n, m;
    init();
    scanf("%d%d", &n, &m);
    for(ll i = 1; i <= n; ++i) {
        ll ki, si;
        scanf("%d%d", &ki, &si);
        k[i] = ki;
        s[i] = si;
        ++in[ki];
        addEdge(ki, i);
    }
    answer(n, m);
    printf("%d\n", dp[0][m+1]);
    return 0;
}